package search;

import static search.SearchFun.searchFun;

/**
 * 折半查找算法
 * 折半查找算法(Binary Search) 又称为二分查找，其要求数据序列呈线性
 * 结构，也就是经过排序的。对于没有经过排序的，可以通过排序算法进行排序
 * 然后执行这边查找操作,具体步骤如下
 * 首先需要三个变量lownum、midnum\highnum，分别保存数组元素的开始、中间和末尾的序列
 * 假定有10个元素，开始时令lownum=0,highnum = 9,midnum = (low+highnum)/2接着进行如下判断:
 * (1)如果序列为midnum的数组元素的值与x相等，表示查找到了数据则返回该序列midnum
 * (2)如果x<a[midnum],表示要查找的数据x位于lownum与midnum-1序号之间，就不需要
 * 再去查找midnum与highnum序号之间的元素了。因此，将highnum变量的值改为midnum-1,
 * 重新查找lownum与midnum-1(即highnum变量的新值)之间的数据。
 * (3)如果x>a[midnum],标识要查找的数据x位于midnum+1与highnum序列之间就不需要
 * 再去查找lownum与midnum序号之间的元素了，因此将lownum变量的值改为midnum-1
 * 重新查找midnum+1(即lownum变量的新值)与highnum之间的数据.
 * (4)逐步循环，如果到lownum>highnum时还未找到目标数据x，则表示无此数据。
 *
 */
public class MidSearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
        int key  = midSearch(arr,arr.length,19);
        System.out.println("搜索到的元素下标:"+key);
    }

    /**
     *
     * @param arr
     * @param size
     * @param key
     * @return
     */
    public static int midSearch(int arr[],int size,int key){
        int low = 0;
        int high = size-1;
        while(low<=high){
          int  mid=(low+high)/2;
            if(arr[mid]==key){
                return mid;
            }else if(arr[mid]>key){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        return -1;
    }
}
